package demo1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: 双指针算法
 * User: LianBao
 * Date: 2024-06-05
 * Time: 21:13
 */
public class Main {
    /**
     * 1. 移动零
     * 链接: https://leetcode.cn/problems/move-zeroes/description/
     *
     * @param nums 题目给的数组
     */
    public void moveZeroes(int[] nums) {
        //双指针:定义dest和cur,dest初始值为-1
        //dest的作用:非0元素的最后一个位置,也就是[0,dest]的区间是非0元素
        //cur的作用:从左往右扫描数组,遍历数组
        int dest = -1;
        int cur = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[cur] != 0) {
                //cur遇到非0元素,先交换dest+1位置和cur位置的元素,再dest++,cur++
                int tmp = nums[dest + 1];
                nums[dest + 1] = nums[cur];
                nums[cur] = tmp;
                dest++;
            }
            cur++;//cur遇到0直接cur++
        }
    }


    /**
     * 2. 复写零
     * 链接: https://leetcode.cn/problems/duplicate-zeros/description/
     * 1、先找到最后一个被复写的元素
     * 1.1 找到最后一个复写的数：也是双指针算法
     * 1. 先
     * 2、从后往前开始复写，定义cur、dest
     *
     * @param arr 题目给的数组
     */
    public void duplicateZeros(int[] arr) {
        int cur = 0;//指向最后一个位置
        int dest = -1;//dest指结果中,最后需要复写的位置,开始时不知道dest在哪,所以-1
        //先找到最后一个被复写的数
        while (cur < arr.length) {
            if (arr[cur] == 0) {
                dest += 2;
            } else {
                dest++;
            }
            if (dest >= arr.length - 1) {
                break;
            }
            cur++;
        }
        //边界情况,可能出现:最后要复写两个0,第二个0在arr.length这个位置
        if (dest == arr.length) {

            arr[arr.length - 1] = 0;
            dest -= 2;
            cur--;
        }
        while (cur >= 0) {

            if (arr[cur] != 0) {
                arr[dest] = arr[cur];
                dest--;
            } else {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
            cur--;
        }
    }

    //快乐数,快慢指针的思想
    /**
     * 求每一位数之和
     * @param n
     * @return
     */
    public int func(int n) {
        int sum = 0;
        while (n != 0) {
            int t = n % 10;
            sum += t * t;
            n /= 10;
        }
        return sum;
    }

    /**
     * 快乐数
     * @param n
     * @return
     */
    public boolean isHappy(int n) {
        int fast = func(n);
        int slow = n;
        while (fast != slow) {
            slow = func(slow);
            fast = func(func(fast));
        }
        return fast == 1;
    }

    //盛最多水的容器

    /**
     * 链接:  https://leetcode.cn/problems/container-with-most-water/
     *
     * @param height 数组
     * @return 返回最大容积
     */
    public int maxArea(int[] height) {
        //根据规律:向内枚举时,要么宽度肯定减小,但是高度只能是不变或减小(木桶效应)
        int left = 0;
        int right = height.length - 1;
        int maxV = 0;
        int V = 0;
        while (left < right) {
            V = (right - left) * Math.min(height[left], height[right]);
            if (V > maxV) {
                maxV = V;
            }
            //让高度小的移动,高度小也叫说明容积小,不符合要求
            if (height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxV;
    }

    /**
     * 有效三角形个数
     *
     * @param nums 给定的数组
     * @return 返回有效三角形个数
     */
    public int triangleNumber(int[] nums) {
        // 利用单调性,使用双指针算法
        int count = 0;
        Arrays.sort(nums);// 先排个序
        int flg = nums.length - 1;//固定好flg,表示最大的数
        while (flg >= 2) {
            //固定好flg之后,再利用双指针
            int left = 0;
            int right = flg - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[flg]) {
                    count += (right - left);
                    right--;
                } else {
                    left++;
                }
            }
            flg--;
        }
        return count;
    }

    /**
     * 两数之和
     *
     * @param price
     * @param target
     * @return
     */
    public int[] twoSum(int[] price, int target) {
        int[] ret = new int[2];
        int left = 0;
        int right = price.length - 1;
        while (left < right) {
            if (price[left] + price[right] < target) {
                left++;
            } else if (price[left] + price[right] > target) {
                right--;
            } else {
                ret[0] = price[left];
                ret[1] = price[right];
                break;
            }
        }
        return ret;
    }

    /**
     * 三数之和
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);//先排序
        int flg = 0;//固定一个的数
        List<List<Integer>> ret = new ArrayList<>();// 返回的List
        while (flg <= nums.length - 2) {
            //双指针算法,left,right
            int left = flg + 1;//左指针
            int right = nums.length - 1;//右指针
            int a = nums[flg];//双指针找目标值和为-a的两个数
            if (a > 0) {
                //小优化,大于0了,后面的都是>0的数,肯定找不到-a
                break;
            }
            //双指针算法,思路和求两数之和一样
            while (left < right) {
                if (nums[left] + nums[right] < (-a)) {
                    left++;
                } else if (nums[left] + nums[right] > (-a)) {
                    right--;
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(a);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    ret.add(list);//
                    // 找到结果之后,left,right跳过重复元素
                    int leftNumber = nums[left];
                    int rightNumber = nums[right];
                    //避免越界
                    while (nums[left] == leftNumber && left < nums.length - 1) {
                        left++;
                    }
                    while (nums[right] == rightNumber && right > 0) {
                        right--;
                    }
                }
            }
            // flg也要跳过重复的元素,flg不能越界
            while (nums[flg] == a && (flg <= nums.length - 2)) {
                flg++;
            }
        }
        return ret;
    }

    /**
     * 四数之和
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();// 返回的List
        for (int i = 0; i < nums.length; ) {//固定数a
            for (int j = i + 1; j < nums.length; ) {//固定数b
                //
                int left = j + 1;
                int right = nums.length - 1;
                long aim = (long) target - (nums[i] + nums[j]);//a+b
                while (left < right) {
                    if (nums[left] + nums[right] < aim) {
                        left++;
                    } else if (nums[left] + nums[right] > aim) {
                        right--;
                    } else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[left]);
                        list.add(nums[right]);
                        list.add(nums[i]);
                        list.add(nums[j]);
                        ret.add(list);
                        //处理细节
                        //避免越界
                        int leftNumber = nums[left];
                        int rightNumber = nums[right];
                        //避免越界
                        while (nums[left] == leftNumber && left < nums.length - 1) {
                            left++;
                        }
                        while (nums[right] == rightNumber && right > 0) {
                            right--;
                        }
                    }
                }

                j++;
                while ((j < nums.length - 2) && nums[j - 1] == nums[j]) {
                    j++;
                }
            }
            i++;
            while ((i < nums.length - 3) && nums[i - 1] == nums[i]) {
                i++;
            }
        }
        return ret;
    }
}
